Search Results

Documents authored by Forbes, Michael A.

Document
DOI: 10.4230/LIPIcs.ICALP.2018.54
Towards Blackbox Identity Testing of Log-Variate Circuits

Authors: Michael A. Forbes, Sumanta Ghosh, and Nitin Saxena

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few variables, eg. logarithmic in the size s. We give the first poly(s)-time blackbox identity test for n=O(log s) variate size-s circuits that have poly(s)-dimensional partial derivative space; eg. depth-3 diagonal circuits (or Sigma wedge Sigma^n). The former model is well-studied (Nisan,Wigderson, FOCS'95) but no poly(s2^n)-time identity test was known before us. We introduce the concept of cone-closed basis isolation and prove its usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration studied extensively in the context of ROABP models.
Cite as

Michael A. Forbes, Sumanta Ghosh, and Nitin Saxena. Towards Blackbox Identity Testing of Log-Variate Circuits. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{forbes_et_al:LIPIcs.ICALP.2018.54,
  author =	{Forbes, Michael A. and Ghosh, Sumanta and Saxena, Nitin},
  title =	{{Towards Blackbox Identity Testing of Log-Variate Circuits}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.54},
  URN =		{urn:nbn:de:0030-drops-90582},
  doi =		{10.4230/LIPIcs.ICALP.2018.54},
  annote =	{Keywords: hitting-set, depth-3, diagonal, derandomization, polynomial identity testing, log-variate, concentration, cone closed, basis isolation}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.30
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs

Authors: Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/k^{O(k)}) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2^{~O(n^{1-1/2^{k-1}})} and needs white box access only to know the order in which the variables appear in the ABP.
Cite as

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 30:1-30:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:LIPIcs.CCC.2016.30,
  author =	{Anderson, Matthew and Forbes, Michael A. and Saptharishi, Ramprasad and Shpilka, Amir and Volk, Ben Lee},
  title =	{{Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{30:1--30:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.30},
  URN =		{urn:nbn:de:0030-drops-58255},
  doi =		{10.4230/LIPIcs.CCC.2016.30},
  annote =	{Keywords: Algebraic Complexity, Lower Bounds, Derandomization, Polynomial Identity Testing}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.32
Proof Complexity Lower Bounds from Algebraic Circuit Complexity

Authors: Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov, which is a function f' from n-bit strings to a field, such that any polynomial f agreeing with f' on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where f'(x) equals 1/p(x) for a constant-degree polynomial p depending on the relevant circuit class. We believe these lower bounds are of independent interest in algebraic complexity, and show that they also imply lower bounds for the size of the corresponding IPS refutations for proving that the relevant polynomial p is non-zero over the boolean cube. In particular, we show super-polynomial lower bounds for refuting variants of the subset-sum axioms in these IPS subsystems. Our second method is to give lower bounds for multiples, that is, to give explicit polynomials whose all (non-zero) multiples require large algebraic circuit complexity. By extending known techniques, we give lower bounds for multiples for various restricted circuit classes such sparse polynomials, sums of powers of low-degree polynomials, and roABPs. These results are of independent interest, as we argue that lower bounds for multiples is the correct notion for instantiating the algebraic hardness versus randomness paradigm of Kabanets and Impagliazzo. Further, we show how such lower bounds for multiples extend to lower bounds for refutations in the corresponding IPS subsystem.
Cite as

Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. Proof Complexity Lower Bounds from Algebraic Circuit Complexity. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{forbes_et_al:LIPIcs.CCC.2016.32,
  author =	{Forbes, Michael A. and Shpilka, Amir and Tzameret, Iddo and Wigderson, Avi},
  title =	{{Proof Complexity Lower Bounds from Algebraic Circuit Complexity}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.32},
  URN =		{urn:nbn:de:0030-drops-58321},
  doi =		{10.4230/LIPIcs.CCC.2016.32},
  annote =	{Keywords: Proof Complexity, Algebraic Complexity, Nullstellensatz, Subset-Sum}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.33
Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity

Authors: Michael A. Forbes, Mrinal Kumar, and Ramprasad Saptharishi

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We say that a circuit C over a field F {functionally} computes a polynomial P in F[x_1, x_2, ..., x_n] if for every x in {0,1}^n we have that C(x) = P(x). This is in contrast to syntactically computing P, when C = P as formal polynomials. In this paper, we study the question of proving lower bounds for homogeneous depth-3 and depth-4 arithmetic circuits for functional computation. We prove the following results: 1. Exponential lower bounds for homogeneous depth-3 arithmetic circuits for a polynomial in VNP. 2. Exponential lower bounds for homogeneous depth-4 arithmetic circuits with bounded individual degree for a polynomial in VNP. Our main motivation for this line of research comes from our observation that strong enough functional lower bounds for even very special depth-4 arithmetic circuits for the Permanent imply a separation between #P and ACC0. Thus, improving the second result to get rid of the bounded individual degree condition could lead to substantial progress in boolean circuit complexity. Besides, it is known from a recent result of Kumar and Saptharishi [Kumar/Saptharishi, ECCC 2015] that over constant sized finite fields, strong enough {average case} functional lower bounds for homogeneous depth-4 circuits imply superpolynomial lower bounds for homogeneous depth-5 circuits. Our proofs are based on a family of new complexity measures called shifted evaluation dimension, and might be of independent interest.
Cite as

Michael A. Forbes, Mrinal Kumar, and Ramprasad Saptharishi. Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{forbes_et_al:LIPIcs.CCC.2016.33,
  author =	{Forbes, Michael A. and Kumar, Mrinal and Saptharishi, Ramprasad},
  title =	{{Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.33},
  URN =		{urn:nbn:de:0030-drops-58266},
  doi =		{10.4230/LIPIcs.CCC.2016.33},
  annote =	{Keywords: boolean circuits, arithmetic circuits, lower bounds, functional computation}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.800
Dimension Expanders via Rank Condensers

Authors: Michael A. Forbes and Venkatesan Guruswami

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
An emerging theory of "linear algebraic pseudorandomness: aims to understand the linear algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension expanders, seeded rank condensers, two-source rank condensers, and rank-metric codes. In particular, with the recent construction of near-optimal subspace designs by Guruswami and Kopparty as a starting point, we construct good (seeded) rank condensers (both lossless and lossy versions), which are a small collection of linear maps F^n to F^t for t<<n such that for every subset of F^n of small rank, its rank is preserved (up to a constant factor in the lossy case) by at least one of the maps. We then compose a tensoring operation with our lossy rank condenser to construct constant-degree dimension expanders over polynomially large fields. That is, we give a constant number of explicit linear maps A_i from F^n to F^n such that for any subspace V of F^n of dimension at most n/2, the dimension of the span of the A_i(V) is at least (1+Omega(1)) times the dimension of V. Previous constructions of such constant-degree dimension expanders were based on Kazhdan's property T (for the case when F has characteristic zero) or monotone expanders (for every field F); in either case the construction was harder than that of usual vertex expanders. Our construction, on the other hand, is simpler. For two-source rank condensers, we observe that the lossless variant (where the output rank is the product of the ranks of the two sources) is equivalent to the notion of a linear rank-metric code. For the lossy case, using our seeded rank condensers, we give a reduction of the general problem to the case when the sources have high (n^Omega(1)) rank. When the sources have constant rank, combining this with an "inner condenser" found by brute-force leads to a two-source rank condenser with output length nearly matching the probabilistic constructions.
Cite as

Michael A. Forbes and Venkatesan Guruswami. Dimension Expanders via Rank Condensers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 800-814, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{forbes_et_al:LIPIcs.APPROX-RANDOM.2015.800,
  author =	{Forbes, Michael A. and Guruswami, Venkatesan},
  title =	{{Dimension Expanders via Rank Condensers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{800--814},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.800},
  URN =		{urn:nbn:de:0030-drops-53379},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.800},
  annote =	{Keywords: dimension expanders, rank condensers, rank-metric codes, subspace designs, Wronskians}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact